package linked_list;

public class DoubleLinkedListDemo {
    public static void main(String[] args) {
        Node2 n1 = new Node2(1, "a");
        Node2 n2 = new Node2(2, "b");
        Node2 n3 = new Node2(3, "c");
        Node2 n4 = new Node2(4, "d");
        DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
        doubleLinkedList.addByOrder(n1);
        doubleLinkedList.addByOrder(n4);
        doubleLinkedList.addByOrder(n2);
        doubleLinkedList.addByOrder(n3);
        doubleLinkedList.show();
        doubleLinkedList.updateNode2(3, "cc");
        doubleLinkedList.show();
        doubleLinkedList.deleteNode2(3);
        doubleLinkedList.show();
    }
}

// 链表定义
class DoubleLinkedList {
    // 创建头节点
    private Node2 head = new Node2(0, "");

    // 在链表末尾添加元素
    public void add(Node2 node) {
        // 找到链表的最后
        Node2 temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        // 加入新节点
        temp.next = node;
        node.pre = temp;
    }

    // 按编号顺序插入节点
    public void addByOrder(Node2 node) {
        // 找到插入位置的前一个节点
        Node2 temp = head;
        while (true) {
            // 若遍历完了整个链表，说明该节点应插入最后
            if (temp.next == null) {
                break;
            }
            // 若temp.next的no大于待插入节点的no，说明插入位置在temp和temp.next之间
            if (temp.next.no > node.no) {
                break;
            } else if (temp.next.no == node.no) {
                System.out.println("已有同编号的节点");
                return;
            }
            temp = temp.next;
        }
        // 添加节点
        node.next = temp.next;
        temp.next = node;
        node.pre = temp;
        if (node.next != null) {
            node.next.pre = node;
        }
    }

    // 更新节点信息
    public void updateNode2(int no, String name) {
        Node2 temp = head;
        while (temp.next != null) {
            if (temp.next.no == no) {
                temp.next.name = name;
                return;
            }
            temp = temp.next;
        }
        System.out.println("未找到该节点");
    }

    // 删除节点
    public void deleteNode2(int no) {
        Node2 temp = head.next;
        while (temp != null) {
            if (temp.no == no) {
                temp.pre.next = temp.next;
                // 如果不加这个if，在删除最后一个节点的时候会报空指针异常
                if (temp.next != null) {
                    temp.next.pre = temp.pre;
                }
                return;
            }
            temp = temp.next;
        }
        System.out.println("未找到该节点");
    }

    // 输出链表
    public void show() {
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        Node2 temp = head.next;
        while (temp != null) {
            System.out.println(temp.toString());
            temp = temp.next;
        }
    }

}

// 节点定义
class Node2 {

    // data域
    public int no;
    public String name;

    // 指针域
    public Node2 next;
    public Node2 pre;

    public Node2(int no, String name) {
        this.no = no;
        this.name = name;
    }

    @Override
    public String toString() {
        return "Node2 [no=" + no + ", name=" + name + "]";
    }
}
